Skip to main content

Full text of "The Interface message processor for the ARPA computer network"

See other formats


KATIE HAFNER I 12 4?6 1966 P.01 
The interface message processor for 
the ARPA computer network' 
b F. E. HEART, R. E. KAHN, S. 5f. ORNSTEIN W. 1L CROWTHER and D.C. WALDEN 
EaU B,aw.k and  
Cbdd, MChtt 
INTRODUCTION 
For many years, smell groups of computers have been 
intercormectcd In various ways. Only recently, how- 
ever, has the interaction of computers and communica- 
tions become an important topic in its om right,** In 
1988, after couslderable preliminary inve:tigation and 
discussion, the Advanced Research Projects 
of the Department of Dcfeitse (ARPA) embarked 
the implementation of a new kind of natiol4de 
computer interconnection knox's as the ARPA 
work. This network 1411 initially intercorinser many 
dimimilar computers at en ARPA-aupported rsearch 
centers ;ith O-kllobit common-carrier circui The 
network may be extended to include many other 
locations and circuits of higher bandwidth. 
Tle primary goal of the AIt. PA project is to permit 
persons and programs at one rcarch center to access 
data and nse interactively programs that exist and 
run in other eomputer of the network. This goal may 
rpresent a major step down the path taken by com- 
puter time-haring, in the scans that the computer 
resources of the rations research centers are thus 
pooled and directly steer, sable to the entire community 
of network participants. 
Study of the technology and tariffs o! available 
commuldeatlona facilities showed that use of con- 
ventlanai lit hinŻ faciRi would be econorfdcaJly 
smi technicaUy inefficient. The traditional method of 
routing io/ormUon through the common-srrler 
switched network establishes a dedicated path for each 
conversation. With present technoloEy, the time 
recltred for this task is on the order of eeŻont. For 
vince commtmition. that overhead time is negligible, 
but in the casa of mny short trausmlsslous, such as 
may occur between computers, that Ume is excessive. 
Therefore, ARPA decided to build a new kind of 
dlgitat coraraunication ystem employing wldeband 
leszed lines and msssc rvithln, wherein a path is 
not established in clvance and each message carries an 
addreSS. In this domain the project portends  possible 
major chane in the character of data communica- 
tion services in the United States. ▀ 
In a naUonwide computer network, economic 
ideratious also mitigate against a wideband leas 
Ene coufiguration that is topologically fully connected. 
I a noa4ully connected network, messages .mUst 
normally traverse several network nodes in lng from 
ruroe to destinatior The ARPA Network is designed 
on this principle and, at eaeh node, a copy of the 
sage is stored until it is safely received at the foilo4ng 
node. The network Is thus a store and forward system 
and es eueh faust deal .4th problems of routing, buffm- 
ing, synchronization, error control, reliability, and 
other related iue To insulate the computer centera 
rom these problems, and to insulate the network from 
the problems of the computer ceuters, ARPA decided 
to place ideaties! small procedars a each network 
node, to Interconnect these small proco, ors with 
leased common-carrier circuits to form a ub/, and 
to connect ech research computer center intO the net 
via the local small pnasor. In this arrangement the 
research computer enters are called Ho and the 
small processors arc called lar. fo Msssas Processors, 
or IMPs. (ee Figu.de L) This approach divides the 
genesks of the Al%PA Network into two parts: (I) 
design and implementorlon of the IMP subnet, sad 
() design and implementation of protocols and teoh- 
nlque for' the sensible utUiation of the network by 
the Heats. 
Implementation of the subnet Involves two major 
------------------------------<page break>-----------------------------
5f gpr 3o,ut Oompuf. e.r nfereoc, lg?O 
Fisua --.The IMP 
usuce, debui;in, and system modification; in normal 
oparation, the IMP runs without any moving parts 
except fa. Withlu the cabinet,, eaca has been re- 
▀erved for an additional 4K memory. Fitre 
picture of an IMP, and 1;tgure 7 shows its confi&ura- 
tion. 
P,ugedisatlon of computer hardware for use in 
friendly environments is aomewhat unusual; howover, 
we fait that the conalderble diHioulty that IMP 
tailttr can cauae the network usgfid this step. 
Although the rugedised unit iz not fully 
to MIL specs, it does have grcatcr resistance to tem- 
perature variance, mechardcs.[ shock and vibration, 
rad/o Irequetcy interference, and power Ibm 
We are confident that this ruggediztion 5ll increase 
the mcan tiwe to failure. 
Modular Hot v. nd modem interfaces ullow au IMP 
to be indlvlduully coufigured for each network node. 
The modulzr/ty, however, does not taka the form of 
plugg&b[e unite and, except for the possibility ol 
addl intface inc reserved frne space, reoon- 
figth-lion is imprOtlcal. Vliotl confi.tratlons allow 
for up  two H and five mems,  H d 
four mc, e. Eh m iaff qr 
pmy onoh e amount of ]oc u 
the C.P.U. o Ht inf is mewhs 
(aut onth of e C.P.u.). 
Inff  e Host and  the ms have 
u common chscds. Both are fl dupl, 
 may be pah unde pmm control 
t thor opation, and th function in the 
genial er. To  s pct, e IMP pm 
ee up memo inm  the pket d 
scva e ins a a pro.stainable conl 
pul. The  k ive wo from 
mo  i ed output data chnel d 
tr em bily ( e Hm or  the 
mem). eu the mo bu h  
pti. the ine uo the pmm s 
inpt ths the job   mple. To 
infoon, the pmm t  in  
la spa in e mcmo in which e [orma- 
tion   flow. U a contl pulse it then 
the ice  ive. When ioto ar 
ve (h Mn bisey), it is mbl in 
lblt wo d s iu e IMP memory. When 
er e 1 memo   full or the d of 
the da tn is de, e inn nofi 
pmrm   inpt. 
e m inf dl th the phon lln 
rms of bi chac; e inaem idle by asndi 
 rn a sync tn at k them in chc- 
r c. Bit sc is n by the me them- 
Iv, which pde th  a ve olk- 
iS als  e nfa Wen the prm itlas 
------------------------------<page break>-----------------------------
50 SprLg Joint Computsr Couferenee, 1970 
TABLE I--Prcra Data Structures 
000 WORDS--MESSAGE BUFFER STORAGE 
10 WORD--UEUE POIITEP, S 
00 WORDSTRACE BLOCKS 
IO WORDS--REASEM. BLY BLOCKS 
1//) WORDS--ROUTIN0 TABLES 
t00 WORDS--LNK TABLES 
00 WORD,--TATiSTICS TABLES 
contains the remaining five programs ad deals with 
lnitilsetion, debugring, ti, stat gatheHn 
d ng. Afar a bcf dcptton of da s 
t, we will di pket pg in some detail, 
Bu/fer nlloctlon, queuos, and tablos 
The major system data structurca (t Tahle 
Mht of buff and bl. The buffer srage space 
is pon in aut 70  length bugle, ch 
of which is  {or sn[  single packet. An unwed 
ber b chsin on ▀ irm buffer t and is moved 
from this list wh it is n  store an incoming 
pkc A packet, once s in s buffer,  nev 
move. AI  pket h n eucctully p 
along  i Ht or  toer IMP, i buffer 
.t  the f It. Tho buffer ep  
tn such s way at each p (sre and 
c, mt sffic, c.)  always gr 
ben. For the e of program a and mpliclty, 
no atmpt Is made  meve e space w by 
pially fitl buffera. 
In hdfing are and fom'a trc, all png 
ts on a r packet bs. Fh, aithoh trc 
ad from Ho b com of mz, the IMP 
piy n  ding  packe; the Host 
aml a mge  a ngle ut but the IMP 
km it e buff a ▀ time. As each buffer is fill, 
▀ e prelim  othcr buffer for input until the 
entire me h n pmd for. Three sueive 
buffera H, in geneS, be t throughout the 
m. Au valent invoke p  on 
output to the Host af all pke of the ma[e 
have siv st the dfition IMP. No itmpt 
er me  11t e peb of ▀ me 
ngo }on of the memory. 
Buffore currently in use e thcr dcs 
in.ming or an outin packet, chsin on ▀ queue 
awtlng ping by the pgr, or inl prd. 
Oclichilly, g buffer may  simulnusly found on 
two queues;  slt